#include <bits/stdc++.h>

using namespace std;

// 含有嵌套的表达式求值
// 测试链接 : https://leetcode.cn/problems/basic-calculator-iii/

class Solution 
{
private:
    int where;

    void push(vector<int>& numbers, vector<char>& ops, int cur, char op)
    {
        int n = numbers.size();
        if(n == 0 || ops[n - 1] == '+' || ops[n - 1] == '-')
        {
            numbers.emplace_back(cur);
            ops.emplace_back(op);
        }
        else
        {
            int topNumber = numbers[n - 1];
            char topOp = ops[n - 1];
            if(topOp == '*')
                topNumber *= cur;
            else
                topNumber /= cur;
            numbers[n - 1] = topNumber;
            ops[n - 1] = op;
        }
    }

    // s[i....]开始计算，遇到字符串终止 或者 遇到)停止
	// 返回 : 自己负责的这一段，计算的结果
	// 返回之间，更新全局变量where，为了上游函数知道从哪继续！
    int f(string& s, int i)
    {
        int cur = 0;
        vector<int> numbers;
        vector<char> ops;
        while(i < s.size() && s[i] != ')')
        {
            if(s[i] >= '0' && s[i] <= '9')
            {
                cur = 10 * cur + s[i++] - '0';
            }
            else if(s[i] != '(')
            {
                // 遇到了运算符 + - * /
                push(numbers, ops, cur, s[i++]);
                cur = 0;
            }
            else
            {
                // 遇到了左括号
                cur = f(s, i + 1);
                i = where + 1;
            }
        }
        push(numbers, ops, cur, '+');
        where = i;
        return compute(numbers, ops);
    }

    int compute(vector<int>& numbers, vector<char>& ops)
    {
        int n = numbers.size();
        int ans = numbers[0];
        for(int i = 1; i < n; ++i)
        {
            ans += ops[i - 1] == '+' ? numbers[i] : -numbers[i];
        }
        return ans;
    }

public:
    int calculate(string s) 
    {
        where = 0;
        return f(s, 0);
    }
};